//给定两个用链表表示的整数，每个节点包含一个数位。 
// 这些数位是反向存放的，也就是个位排在链表首部。 
// 编写函数对这两个整数求和，并用链表形式返回结果。 
//
// 
//
// 示例： 
//
// 
//输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
//输出：2 -> 1 -> 9，即912
// 
//
// 进阶：假设这些数位是正向存放的，请再做一遍。 
//
// 示例： 
//
// 
//输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
//输出：9 -> 1 -> 2，即912
// 
// Related Topics 链表 数学 
// 👍 26 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.List;

//Java：链表求和
public class P0205SumListsLcci {
    public static void main(String[] args) {
        Solution solution = new P0205SumListsLcci().new Solution();
        ListNode node1 = new ListNode(7);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(9);
        ListNode node6 = new ListNode(2);
        node4.next = node5;
        node5.next = node6;
        node6.next = null;

        ListNode res = solution.addTwoNumbers(node1, node4);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null){
                return l2;
            }
            if(l2==null){
                return l1;
            }

            /*
            需要注意几个测试用例：
            1 进位如何处理
            2 长度不同如何处理
            3 最后一位出现进位如何处理
            写代码之前一定要自己写出结果测试用例来
            3+4
            5+5
            1+99

            * */
            ListNode dumpty=new ListNode(0);
            ListNode node=dumpty;
            int sum=0,num=0,addIndex=0;
            while(l1!=null||l2!=null){
                int val1=(l1!=null)?l1.val:0;
                int val2=(l2!=null)?l2.val:0;
                sum=val1+val2+addIndex;//注意这里的sum是要加余数的
                num=sum%10;
                addIndex=sum/10;
                node.next=new ListNode(num);
                node=node.next;
                l1=(l1!=null)?l1.next:null;
                l2=(l2!=null)?l2.next:null;

            }

            if(addIndex!=0){
                node.next=new ListNode(addIndex);
            }

            return dumpty.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}